package liwenxia.com.tree_learn.demo1;

import sun.reflect.generics.tree.Tree;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class BTTraversal {



    /*
    生成树
     */

    public static void CreateTree(int value, TreeNode tree) {
        // 如果当前二叉树是空的，拿第一个元素做头节点
        if (tree.value == 0) {
            tree.setValue(value);
        }
        // 小放左，相等暂时不用管
        if (tree.value > value) {
            if (tree.left == null) {
                // 如果左节点空，直接设置
                TreeNode leftTree = new TreeNode();
                leftTree.setValue(value);
                //tree.left(leftTree);
            } else if (tree.left != null) {
                // 如果左节点不为空，递归调用继续找左节点数据比较大小
                CreateTree(value, tree.left);
            }
        }
        // 大放右，相等暂时不用管
        if (tree.value < value) {
            if (tree.right == null) {
                TreeNode rightTree = new TreeNode();
                rightTree.setValue(value);
                // tree.setRight(rightTree);
            } else if (tree.right != null) {
                CreateTree(value, tree.right);
            }
        }
    }

    TreeNode root = null;

    /*
    中序遍历
     */
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inoder(root, list);
        return list;
    }

    public void inoder(TreeNode root, List list) {
        //如果节点为空，直接退出循环
        if (root == null) {
            return;
        }
        inoder(root.left, list);//访问左子树
        list.add(root.value);//将节点的值存入到list中
        inoder(root.right, list);//访问右子树

    }

    /*
    查找操作
     */
    public TreeNode find(int key) {
        TreeNode cur = root;
        while (cur != null) {
            if (key < cur.key) {
                cur = cur.left;
            } else if (key > cur.key) {
                cur = cur.right;
            } else {
                return cur;
            }
        }
        return null;
    }

    /*
    插入操作
     */
    public TreeNode insert(int key, int value) {
        if (root == null) {
            root = new TreeNode(key, value);
            return root;
        }

        TreeNode cur = root;
        TreeNode prev = null;
        while (cur != null) {
            if (key < cur.key) {
                prev = cur;
                cur = cur.left;
            } else if (key > cur.key) {
                prev = cur;
                cur = cur.right;
            } else {
                //找到了key相同的元素
                //此处吧value改为新的value
                cur.value = value;
                return cur;
            }
        }
        TreeNode newNode = new TreeNode(key, value);
        if (newNode.value < prev.key) {
            prev.left = newNode;
        } else {
            prev.right = newNode;
        }
        return newNode;
    }


    /*
    删除操作
     */
    public void remove(int key) {
        TreeNode cur = root;
        TreeNode parent = null;
        while (cur != null) {
            if (key < cur.key) {
                parent = cur;
                cur = cur.left;
            } else if (key > cur.key) {
                parent = cur;
                cur = cur.right;
            } else {
                removeNode(cur, parent);
                return;
            }
        }
    }

    public void removeNode(TreeNode cur, TreeNode parent) {
        if (cur.left == null) {
            if (cur == root) {
                root = cur.right;
            } else if (cur == parent.left) {
                parent.left = cur.right;
            } else if (cur == parent.right) {
                parent.right = cur.right;
            }
        } else if (cur.right == null) {
            if (cur == root) {
                root = cur.left;
            } else if (cur == parent.left) {
                parent.left = cur.left;
            } else if (cur == parent.right) {
                parent.right = cur.left;
            }
        } else {
            TreeNode scapeGoat = cur.right;
            TreeNode scapeGoatParent = cur;
            while (scapeGoat.left != null) {
                scapeGoatParent = scapeGoat;
                scapeGoat = scapeGoat.left;
            }
            cur.key = scapeGoat.key;
            cur.value = scapeGoat.value;
            if (scapeGoat == scapeGoatParent.left) {
                scapeGoatParent.left = scapeGoat.right;
            } else {
                scapeGoatParent.right = scapeGoat.right;
            }
        }
    }


    public static void main(String[] args) {

        /**
         * -----------------------------------------------------------
         */

        Scanner scanner = new Scanner(System.in);

        Boolean flag = true;

        /**
         * 每次命令之前可以加一些提示信息
         */
        while (true) {
            System.out.println("请输入命令：");
            flag = true;
            if (scanner.hasNextLine()) {
                String cmd = scanner.nextLine();
//                System.out.println(cmd);

                switch (cmd) {
                    case "insert":
                        System.out.println("insert");//具体的业务逻辑
                        break;
                    case "delete":
                        System.out.println("delete");
                        break;
                    case "select":
                        System.out.println("select");
                        break;
                    case "exit":
                        flag = false;
                        break;
                    default:
                        System.out.println("请输入正确的命令：");
                        break;
                }
                /**
                 * 如果输入exit 就退出
                 */
                if (!flag) {
                    break;
                }
            }
        }
    }

    private static void FindTreeValue(TreeNode createdTree, int i, int i1) {
    }
}
